// https://leetcode.cn/problems/evaluate-boolean-binary-tree/description/
// /**
// 计算布尔二叉树的值
//  * Definition for a binary tree node.
//  * struct TreeNode {
//  *     int val;
//  *     TreeNode *left;
//  *     TreeNode *right;
//  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//  * };
//  */
// class Solution {
// public:
//     bool evaluateTree(TreeNode* root) {
//         //递归函数的作用是，返回这个节点的左子树和右子树的运算结果
//         if(root == nullptr)
//         {
//             return true;
//         }
//         bool left = evaluateTree(root->left);
//         bool right= evaluateTree(root->right);
//         if(root->val == 2)
//         {
//             return left | right;
//         }
//         else if(root->val == 3)
//         {
//             return left & right;
//         }
//         else if(root->val == 1)
//         {
//             return true;
//         }
//         else
//         {
//             return false;
//         }
//     }
// };


//https://leetcode.cn/problems/sum-root-to-leaf-numbers/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
//求根节点到叶子节点的数之和
// class Solution {
// public:
//     int sumNumbers(TreeNode* root) { return dfs(0, root); }
//     //
//     int dfs(int nums, TreeNode* root) {
//         int num = nums * 10 + root->val;
//         if (root->left == nullptr && root->right == nullptr) {
//             return num;
//         }
//         int ret = 0;
//         if (root->left) {
//             ret += dfs(num, root->left);
//         }
//         if (root->right) {
//             ret += dfs(num, root->right);
//         }
//         return ret;
//     }
// };


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */



// https://leetcode.cn/problems/binary-tree-pruning/
//二叉树的剪枝
// class Solution {
// public:
//     TreeNode* pruneTree(TreeNode* root) {
//         //当子问题不明确的时候，我们怎么写递归函数?
//         //此时我们不关系我们的递归函数要做什么，我们需要写出函数头，已经函数体，和返回值,通过决策树模拟的过程确定
//         //只有后序遍历的时候我们才会知道左右两边子树的情况
//        return dfs(root);
//     }
//     TreeNode* dfs(TreeNode* root)
//     {
//         if(root==nullptr)
//         {
//             return nullptr;
//         }
//         root->left = dfs(root->left);
//         root->right = dfs(root->right);
//         if(root->left==nullptr && root->right==nullptr && root->val == 0)
//         {
//             return nullptr;
//         }
//         else
//         {
//             return root;
//         }
//     }
// };




/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */

// class Solution {
// public:
//     long prev = LONG_MIN; // 前驱节点
//     bool isValidBST(TreeNode* root) {
//         // 我们的递归函数判断的是左右两边的树是不是二叉搜索树
//         return dfs(root);
//     }
//     bool dfs(TreeNode* root) {
//         if(!root)
//         {
//             return true;
//         }
//         bool left = dfs(root->left);
//         bool cur = false;
//         if (root->val > prev) {
//             prev = root->val;
//             cur = true;
//         } 
//         else {
//             cur = false;
//         }
//         bool right = dfs(root->right);
//         return right && left && cur;
//     }
// };

//在二叉树的前中后序遍历的语境里面递归的函数的意思是遍历玩左右两边的子树
